Méthode de type off-policy avec approximations

5. Aspect géométrique des fonctions des valeurs

Pour mieux comprendre le problème d'instabilité dans l'apprentissage de type off-policy, il peut être utile d'étudier les fonctions d'approximation linéaires de manière plus abstraite et indépendamment de la manière dont l'apprentissage est réalisé. Pour cela, on peut imaginer l'espace de l'ensemble des fonctions des valeurs des états, c'est-à-dire toutes les fonctions $v \in S$ qui un état donnent un nombre réel $v:S \to \mathbb{R}$. La plupart de ces fonctions ne sont pas en rapport avec des stratégies. Plus important encore, la plupart d'entre elles ne sont pas représentables par des approximations de fonctions qui par construction ont beaucoup moins de paramètres que le nombre d'états de l'environnement.

Espace vectoriel des fonctions des valeurs des états linéaires

Dans le cas où l'espace des états est fini, par exemple $S = \left\{ {{s_1},{s_2},{s_{3,}}...,{s_{\left| S \right|}}} \right\}$, alors à chaque état $s \in S$ correspond une valeur $v(s)$ et un vecteur correspondant à l'empilement de ces valeurs ${[v({s_1}),v({s_2}),...,v({s_{\left| s \right|}})]^T}$. Ce vecteur possède donc autant de composantes qu'il y a d'états dans l'environnement, ce qui peut rendre impossible une représentation exacte avec les approximations de fonctions.

Pour développer notre intuition, considérons le cas où l'environnement possède trois états $S = \left\{ {{s_1},{s_2},{s_3}} \right\}$ et notre fonction d'approximation deux paramètres $\textbf{w} = {\left( {{w_1},{w_2}} \right)^T}$. On peut alors visualiser l'ensemble des vecteurs résultants de l'application des fonctions des valeurs des états sur les états de l'environnement comme des points dans un espace à trois dimensions. Les paramètres $(w_1,w_2)$ du vecteur poids $\textbf w$ sont alors un sous-espace vectoriel à 2 dimensions de cet espace à 3 dimensions. Chaque vecteur poids $\textbf{w} = {\left( {{w_1},{w_2}} \right)^T}$ est un point dans le sous-espace vectoriel à deux dimensions, à laquelle une fonction des valeurs des états $v_{\textbf{w}}$ attribue une valeur aux trois états $(s_1,s_2,s_3)$. Avec des approximations de fonctions générales, les relations entre le sous-espace vectoriel à 2 dimensions et l'espace complet à 3 dimensions peuvent être très complexes. Mais avec des approximations linéaires, le sous-espace vectoriel est un simple plan qui contient l'ensemble des fonctions d'approximation est l'espace engendré par les vecteurs poids et est donc également à deux dimensions:

Espace vectoriel des fonctions des valeurs des états non linéaires

Considérons maintenant une stratégie $\pi$ et considérons que la fonction des valeurs des états $v_\pi$ selon cette stratégie est trop complexe pour être approximée de manière exacte. Dans ce cas, $v_\pi$ n'appartient pas au sous-espace vectoriel en 2 dimensions précédent:

Or, si $v_\pi$ ne peut pas être représentée de manière exacte, quelle est son approximation la plus exacte possible ?

Mesure des fonctions des valeurs des états

Pour répondre à cette question, il nous faut une définir une mesure permettant de mesurer la distance entre deux fonctions des valeurs des états. La mesure conventionnelle (norme euclidienne) n'est pas appropriée ici car certains états sont plus importants que d'autres car ils apparaissent plus fréquemment où qu'ils ont un impact plus important que les autres états. On fait donc intervenir la distribution $\mu :S \to \left[ {0,1} \right]$ qui quantifie le degré avec lequel chaque état est plus ou moins bien évalué (à quelle fréquence celui-ci apparait dans la distribution on-policy). On définit donc la norme d'une fonction des valeurs des états de la manière suivante:

$$\left\| v \right\|_\mu ^2 = \sum\limits_{s \in S} {\mu \left( s \right)v{{\left( s \right)}^2}}$$

On retrouve donc notre fameuse fonction objectif que nous avions défini précédemment et qui permet de mesurer la distance entre deux fonctions des valeurs des états :

$$\overline {VE} (\textbf{w}) = \left\| {{v_\pi } - {v_\textbf{w}}} \right\|_\mu ^2 = {\sum\limits_{s \in S} {\mu \left( s \right)\left[ {{v_\pi }(s) - {v_\textbf{w}}(s)} \right]} ^2}$$

Approximation la plus juste

Pour trouver l'approximation la plus juste de $v_\pi$, il faut utiliser l'opérateur de projection $\prod$ :

$${\prod _{{v_\pi }}} = {v_\textbf{w}}{\rm{ \quad tel \: que\: \: }}\textbf{w} = \mathop {\arg \min }\limits_{\textbf{w} \in {\mathbb{R}^d}} \left\| {{v_\pi } - {v_\textbf{w}}} \right\|_\mu ^2$$

C'est cette fonction des valeurs des états vers lesquelles tendent de manière asymptotique les méthodes de Monte Carlo, mais de manière souvent très lentes.

Erreur de Bellman

Les méthodes par différences temporelles permettent de trouver d'autres solutions. Pour le comprendre, rappelons ci-dessous l'équation de Bellman pour la fonction des valeurs des états $v_\pi$:

$${v_\pi }\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right)\sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {v_\pi }\left( {s'} \right)} \right]} }$$

La vraie fonction des valeurs des états $v_\pi$ est a seule fonction solution de l'équation précédente. Si une fonction approximée $v_\textbf{w}$ est utilisée, alors on peut introduire l'erreur de Bellman sur l'état $s$ qui permet de mesurer de combien sont éloignées les valeurs données par les deux fonctions $v_\pi$ et $v_\textbf{w}$ sur un état $s$ spécifique :

$${\overline \delta _\textbf{w}}\left( s \right) = \left( {\sum\limits_a {\pi \left( {a|s} \right)\sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {v_\textbf{w}}\left( {s'} \right)} \right]} } } \right) - {v_\textbf{w}}\left( s \right)$$

$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = {E_\pi }\left[ {{R_{t + 1}} + \gamma {v_\textbf{w}}\left( {{S_{t + 1}}} \right) - {v_\textbf{w}}\left( {{S_t}} \right)|{S_t} = s,{A_t} \sim \pi } \right]$

L'erreur de Bellman correspond donc à l'espérance de l'erreur TD.

Opérateur de Bellman

L'opérateur de Bellman est définit de la manière suivante :

$$\left( {{B_\pi }v} \right)\left( s \right) = \sum\limits_a {\pi \left( {a|s} \right)\sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {v}\left( {s'} \right)} \right]} }$$

L'application de l'opérateur de Bellman à une fonction des valeurs des états appartenant au sous-espace vectoriel des fonctions d'approximation va en général produire une nouvelle fonction des valeurs des états en dehors de ce sous-espace vectoriel:

Vecteur erreur de Bellman

Le vecteur construit à partir de l'ensemble des erreurs de Bellman, pour l'ensemble des états de l'environnement, est appelée le vecteur erreur de Bellman.

Le vecteur erreur de Bellman peut être écrit à partir de l'opérateur de Bellman :

$${\overline \delta _\textbf{w}} = {B_\pi }{v_\textbf{w}} - {v_\textbf{w}}$$

Valeur quadratique moyenne de l'erreur de Bellman

La norme du vecteur de l'erreur de Bellman est appelée la valeur quadratique moyenne de l'erreur de Bellman :

$$\overline {BE} \left( \textbf{w} \right) = \left\| {{{\overline \delta }_\textbf{w}}} \right\|_\mu ^2$$

Il est impossible en général de réduire $\overline {BE}$ à zéro (ce qui engendrerait $v_\textbf{w} = v_\pi$), mais dans le cas des approximations linéaires il existe une unique valeur de $\textbf{w}$ pour laquelle $\overline {BE}$ est minimale. Ce point appartient donc au sous-espace vectoriel en 2 dimension de l'ensemble des fonctions d'approximations :

Cas de la méthode par programmation dynamique

Dans le cadre de la méthode par programmation dynamique (sans approximations de fonctions), l'opérateur de Bellman est appliqué de manière répétitive sur des points en dehors de l'espace vectoriel des fonctions linéaires, jusqu'à convergence (éventuelle) vers la vraie valeur de la fonction $v_\pi$ :

Cas des méthodes par différences temporelles avec approximations de fonctions

Lorsque les approximations de fonctions sont utilisées, les fonctions des valeurs des états intermédiaires n'appartiennent pas à l'espace vectoriel qui contient $v_\pi$. En effet, après la première itération de mise à jour, la fonction des valeurs des états doit être projetée dans le sous-espace vectoriel pour qu'elles puissent être correctement représentées.

Lors de l'itération suivante, cette projection est ensuite renvoyée dans l'espace vectoriel général à l'aide de l'application de l'opérateur de Bellman puis re-projetée dans le sous-espace vectoriel. C'est ainsi que fonctionne les méthodes par différences temporelles avec approximations de fonctions :

Projeté du vecteur erreur de Bellman

Ce qui nous intéresse dans le cas des méthodes par différences temporelles avec approximation des fonctions est donc d'évaluer la norme de la projection du vecteur erreur de Bellman dans le sous-espace vectoriel auquel appartiennent les fonctions d'approximations. C'est ce qu'on appelle le projeté du vecteur erreur de Bellman (PBE) : $\prod {\overline \delta _{{v_\textbf{w}}}}$

La norme de ce vecteur est une autre mesure permettant d'évaluer l'erreur commise par l'approximation de fonctions sur la fonction des valeurs des états. Elle est définit par la valeur moyenne quadratique du vecteur projeté de l'erreur de Bellman :

$$\overline {PBE\left( \textbf{w} \right)} = \left\| {\prod {{\overline \delta }_{{v_\textbf{w}}}}} \right\|_\mu ^2$$

Dans le cas des approximations linéaires des fonctions, il existe toujours une fonction d'approximation de la valeur des états appartenant au sous-espace vectoriel dont la valeur $\overline {PBE} = 0$. C'est le point fixe $w_{TD}$ que nous avions introduit lors de l'étude de la méthode par semi-gradient. Cette valeur est généralement différente de celle qui minimise la fonction objectif $\overline {VE}$ ou la valeur de l'erreur du vecteur de Bellman $\overline {BE}$. Les méthodes qui garantissent la convergence vers ce point vont être étudiées par la suite.